package other;

/**
 * 数学：快速幂
 * 创建时间：2024-03-20 15:49
 * 地址：https://oi-wiki.org/math/binary-exponentiation/
 */
public class 快速幂 {

    public static long fastPow(long a, long b) {
        long res = 1;
        while(b > 0) {
            // 判断最低位是否为1
            if ((b & 1) > 0) {
                res *= a;
            }
            // 平方
            a = a * a;
            // 指数做右移
            b >>= 1;
        }
        return res;
    }

    /**
     * 应用:模意义下取幂
     * 取模的运算不会干涉乘法运算，因此只需要在计算的过程中取模即可
     *
     * @param a 底数
     * @param b 指数
     * @param m 模
     * @return 结果
     */
    public static long binPow(long a, long b, long m) {
        long res = 1;
        while(b > 0) {
            // 判断最低位是否为1
            if ((b & 1) > 0) {
                res = res * a % m;
            }
            // 平方
            a = a * a;
            // 指数做右移
            b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(fastPow(29, 9));
    }
}
